import java.util.HashMap;
import java.util.Objects;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 74646
 * Date: 2022-03-27
 * Time: 20:46
 */
class Person{
    public String ID;
    public Person(String ID){
        this.ID = ID;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return Objects.equals(ID, person.ID);
    }

    @Override
    public int hashCode() {
        return Objects.hash(ID);
    }

    @Override
    public String toString() {
        return "Person{" +
                "ID='" + ID + '\'' +
                '}';
    }
}

public class HashBuck<K,V> {
    //静态类：结点
    static class Node<K,V>{
        public K key; //存放的元素
        public V val; //元素出现的次数
        public HashBuck.Node<K,V> next;
        public Node(K key,V val){
            this.key = key;
            this.val = val;
        }
    }
    public static final double DEFAULT_LOAD_FACTOR = 0.75; //定义负载因子（负载因子一般情况不能改变）

    public Node<K,V>[] array =(Node<K, V>[]) new Node[10];
    public int usedSize; //元素的个数

    public void put(K key,V val){
        //1、找到key所在的位置
        //需要借助hashCode方法将引用类型的数组转换为整型
        int hash= key.hashCode();
        int index = hash % this.array.length;

        //2、遍历key所在下标的链表，看是否有相同的key，如果有就更新val值
        HashBuck.Node<K,V> cur = array[index];
        while (cur!=null){
            // key 是引用类型的数据，所以需要用 equals 比较
            // 而 equals 方法在重写 hashCode方法的时候，就已经捆绑重写了
            if(cur.key.equals(key)){
                cur.val = val; //有相同的key，更新val值
            }
            cur = cur.next;
        }

        //3、如果没有这个值就进行结点的插入
        HashBuck.Node<K,V> node = new HashBuck.Node<>(key,val);
        node.next = array[index];
        array[index] = node;
        this.usedSize++;

        //4、插入元素成功之后，检查当前散列表的负载因子
        if(loadFactor()>DEFAULT_LOAD_FACTOR) {
            resize();
        }
    }

    //扩容
    private void resize(){
        //扩容需要重新哈希
        HashBuck.Node<K,V>[] newArray = (Node<K, V>[])new HashBuck.Node[array.length*2];
        for (int i = 0; i < array.length; i++) {
            HashBuck.Node<K,V> cur = array[i];
            while (cur!=null){
                int hash= cur.key.hashCode();
                int index = hash % newArray.length; //获取扩容后key所在的位置
                //在扩容后的数组中进行头插或尾插(这里使用的是头插法）
                HashBuck.Node<K,V> curNext = cur.next; //记录原数组中下一个结点的位置
                cur.next = newArray[index]; //先绑定后面
                newArray[index] = cur; //绑定前面
                cur = curNext;
            }
        }
        array = newArray; //原数组引用新的数组
    }

    //计算负载因子
    private double loadFactor(){
        return 1.0*usedSize / array.length;  //负载因子 = 散列表中的元素个数 / 散列表的长度
    }

    public V get(K key){
        //1、找到key所在的位置
        int hash= key.hashCode();
        int index = hash % this.array.length;
        // 2、遍历数组，寻找 key
        HashBuck.Node<K,V> cur = array[index];
        while (cur!=null){
            if(cur.key.equals(key)){
                return cur.val;
            }
            cur = cur.next;
        }
        return null;
    }

    public static void main(String[] args) {

        HashMap<String,Integer> map = new HashMap<>(19);

        Person person1 = new Person("123");
        Person person2 = new Person("123");
        HashBuck<Person,String> hashBuck = new HashBuck<>();
        //将ID放入person1中，获取person2中的value值
        //如果person1 与 person2的ID相同，那么获取的person2中的value值就是person1中存放的ID
        hashBuck.put(person1,"CSDN");
        System.out.println(hashBuck.get(person2));
    }
}
